package com.zs.letcode.trie;

import org.springframework.cglib.proxy.Factory;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 回文对
 * 给定一组 互不相同 的单词， 找出所有 不同的索引对 (i, j)，使得列表中的两个单词，words[i] + words[j]，可拼接成回文串。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：words = ["abcd","dcba","lls","s","sssll"]
 * 输出：[[0,1],[1,0],[3,2],[2,4]]
 * 解释：可拼接成的回文串为 ["dcbaabcd","abcddcba","slls","llssssll"]
 * 示例 2：
 * <p>
 * 输入：words = ["bat","tab","cat"]
 * 输出：[[0,1],[1,0]]
 * 解释：可拼接成的回文串为 ["battab","tabbat"]
 * 示例 3：
 * <p>
 * 输入：words = ["a",""]
 * 输出：[[0,1],[1,0]]
 * <p>
 * 提示：
 * <p>
 * 1 <= words.length <= 5000
 * 0 <= words[i].length <= 300
 * words[i] 由小写英文字母组成
 * 相关标签
 * 字典树
 * 数组
 * 哈希表
 * 字符串
 * <p>
 * Python3
 * <p>
 * <p>
 * <p>
 * 作者：力扣 (LeetCode)
 * 链接：https://leetcode-cn.com/leetbook/read/trie/x75mhj/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 *
 * @author madison
 * @description
 * @date 2021/8/7 10:18
 */
public class Chapter7 {
    public static void main(String[] args) {

    }

    private static class Solution {
        /**
         * 方法一：枚举前缀和后缀
         * 下面给出的是使用字典树的代码：
         */
        private class Node {
            int[] ch = new int[26];
            int flag;

            public Node() {
                flag = -1;
            }
        }

        List<Node> tree = new ArrayList<>();

        public List<List<Integer>> palindromePairs(String[] words) {
            tree.add(new Node());
            int n = words.length;
            for (int i = 0; i < n; i++) {
                insert(words[i], i);
            }
            List<List<Integer>> ret = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                int m = words[i].length();
                for (int j = 0; j <= m; j++) {
                    if (isPalindrome(words[i], j, m - 1)) {
                        int leftId = findWord(words[i], 0, j - 1);
                        if (leftId != -1 && leftId != i) {
                            ret.add(Arrays.asList(i, leftId));
                        }
                    }
                    if (j != 0 && isPalindrome(words[i], 0, j - 1)) {
                        int rightId = findWord(words[i], j, m - 1);
                        if (rightId != -1 && rightId != i) {
                            ret.add(Arrays.asList(rightId, i));
                        }
                    }
                }
            }
            return ret;
        }


        private void insert(String s, int id) {
            int len = s.length(), add = 0;
            for (int i = 0; i < len; i++) {
                int x = s.charAt(i) - 'a';
                if (tree.get(add).ch[x] == 0) {
                    tree.add(new Node());
                    tree.get(add).ch[x] = tree.size() - 1;
                }
                add = tree.get(add).ch[x];
            }
            tree.get(add).flag = id;
        }

        private boolean isPalindrome(String s, int left, int right) {
            int len = right - left + 1;
            for (int i = 0; i < len / 2; i++) {
                if (s.charAt(left + i) != s.charAt(right - i)) {
                    return false;
                }
            }
            return true;
        }

        private int findWord(String s, int left, int right) {
            int add = 0;
            for (int i = right; i >= left; i--) {
                int x = s.charAt(i) - 'a';
                if (tree.get(add).ch[x] == 0) {
                    return -1;
                }
                add = tree.get(add).ch[x];
            }
            return tree.get(add).flag;
        }


        /**
         * 方法一：枚举前缀和后缀
         * 下面给出的是使用哈希表的代码：
         */
        public List<List<Integer>> palindromePairs1(String[] words) {
            return null;
        }

        /**
         * 方法二：字典树 + Manacher
         */
        public List<List<Integer>> palindromePairs2(String[] words) {
            return null;
        }

        private class Trie {
            class Node {
                int[] ch = new int[26];
                int flag;

                public Node() {
                    flag = -1;
                }
            }

            List<Node> tree = new ArrayList<>();

            public Trie() {
                tree.add(new Node());
            }

            public void insert(String s, int id) {
                int len = s.length(), add = 0;
                for (int i = 0; i < len; i++) {
                    int x = s.charAt(i) - 'a';
                    if (tree.get(add).ch[x] == 0) {
                        tree.add(new Node());
                        tree.get(add).ch[x] = tree.size() - 1;
                    }
                    add = tree.get(add).ch[x];
                }
                tree.get(add).flag = id;
            }

            public int[] query(String s) {
                int len = s.length(), add = 0;
                int[] ret = new int[len + 1];
                Arrays.fill(ret, -1);
                for (int i = 0; i < len; i++) {
                    ret[i] = tree.get(add).flag;
                    int x = s.charAt(i) - 'a';
                    if (tree.get(add).ch[x] == 0) {
                        return ret;
                    }
                    add = tree.get(add).ch[x];
                }
                ret[len] = tree.get(add).flag;
                return ret;
            }
        }
    }
}
